package com.xizi.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

/**
 * @author xizizzz
 * @description: TODO
 * @date 2021-7-18下午 10:00
 */
public class bucketSort {

    public static void main(String[] args) {
        double[] arr = new double[]{2, 5, 3, 0, 2, 3, 0, 3};
        System.out.println("排序前---------------------");
        System.out.println(Arrays.toString(arr));
        double[] res = bucketSort(arr);
        System.out.println("排序后---------------------");
        System.out.println(Arrays.toString(res));
    }

    public static double[] bucketSort(double[] array) {
        //得到数列的最大值和最小值，并计算出差值d
        double max = array[0];
        double min = array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max, array[i]);
            min = Math.min(min, array[i]);
        }
        double d = max - min;

        //初始化桶
        int bucketNum = array.length;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<Double>());
        }

        //遍历原始数组将每个元素放入桶中
        for (int i = 0; i < array.length; i++) {
            int num = (int) ((array[i] - min) * (bucketNum - 1) / d);
            bucketList.get(num).add(array[i]);
        }

        //对每个桶内部进行排序
        for (int i = 0; i < bucketList.size(); i++) {
            // 使用Collections.sort，其底层实现基于归并排序或归并排序的优化版本
            Collections.sort(bucketList.get(i));
        }

        //输出全部元素
        double[] sortedArray = new double[array.length];
        int index = 0;
        for (LinkedList<Double> list : bucketList) {
            for (double element : list) {
                sortedArray[index] = element;
                index++;
            }
        }
        return sortedArray;
    }

}
